package cn.qyd.leecode;

/**
 * @author 邱运铎
 * leecode 924 减少恶意软件的传播
 * @date 2024-04-17 10:09
 */
public class BadNodeInfect01 {
    private int nodeStatus;
    private int changeNode;
    public static void main(String[] args) {
        BadNodeInfect01 demo = new BadNodeInfect01();
        int[][] graph = {{1,0,0},{0,1,0},{0,0,1}};
        int[] initial = new int[]{0,2};
        int i = demo.minMalwareSpread(graph, initial);
        System.out.println(i);

    }
    public int minMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.length;

        boolean[] visited = new boolean[n];
        boolean[] isInitial = new boolean[n];

        int initialMinNode = n + 1;

        for (int initialBadNode : initial) {
            isInitial[initialBadNode] = true;
            initialMinNode = Math.min(initialBadNode, initialMinNode);
        }
        int removeNode = initialMinNode;
        int maxChange = 0;
        for (int curInitialBadNode : initial) {
           if (!visited[curInitialBadNode]) {
               nodeStatus = -1;
               changeNode = 0;
               dfs(graph, curInitialBadNode, visited, isInitial);

               /**
                * nodeStatus < 0 代表存在其他最初感染节点和当前最初感染节点相连通
                * 这样说明移除该最初感染节点不会改变最终感染节点数，所以不处理
                * nodeStatus >= 0 代表当前最初感染节点是一个独立的，一旦移除可以影响到最终感染节点数
                * changeNode 代表当前最初感染节点可以感染的所有节点（包括自己）
                * 代表一旦移除当前最初感染节点，会使得最终感染节点数少 badNodeNum个

                * changeNode > maxChange 代表当前最初感染节点影响的节点数截止到当前是最多的，进入if 更新当前最大感染节点数，和节点id
                * changeNode == maxChange && curInitialBadNode < removeNode 代表当前最初感染节点影响的节点数和目前最大的影响节点数相同，
                * 并且当前节点的id小于之前影响最大节点数的节点id,同样需要进入方法更新节点id
                */
               if (nodeStatus >= 0 && changeNode >maxChange || (changeNode == maxChange && curInitialBadNode < removeNode)) {
                   removeNode = curInitialBadNode;
                   maxChange = changeNode;
               }
           }
        }
        return  removeNode;
    }

    public void dfs(int[][] graph, int curNode, boolean[] visited, boolean[] isInitial) {
        changeNode++;
        visited[curNode] = true;

        // 当前最初感染节点的状态 初始 -1 ， 第一次扫描到 变为最初感染节点id, 第二次扫描到后变为-2 之后不在进入。
        // 当发现该最初感染节点可以和其他最初感染节点相连接，
        // 则放弃该节点为，主要通过设置curNode=-2代表后续不处理该节点
        if (nodeStatus != -2 && isInitial[curNode]) {
            nodeStatus = nodeStatus == -1 ? curNode : -2;
        }

        for (int i = 0; i < graph[curNode].length; i++) {
            if (!visited[i] && graph[curNode][i] == 1) {
                dfs(graph, i, visited, isInitial);
            }
        }
    }
}
